Predicate Logic.html (2863B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.0.3 (456341)"/><meta name="keywords" content="logic"/><meta name="altitude" content="-1.601898908615112"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-03-13 15:34:56 +0000"/><meta name="latitude" content="52.33283313851265"/><meta name="longitude" content="4.866307919883771"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-03-13 16:02:49 +0000"/><title>Predicate Logic</title></head><body><div><b>Atomic formulas</b></div><div>role of propositional vars p,q,r is taken over by atomic formulas with objects and predicates</div><div><br/></div><div>C(j)</div><div><ul><li>C is a unary predicate symbol</li><li>can mean e.g. Jane (j) is clever (C)</li></ul><div><br/></div></div><div>K(a,b)</div><div><ul><li>K is a binary predicate symbol</li><li>can mean e.g. A knows B</li><li>A and B are objects a and b</li></ul><div><br/></div></div><div><b>Quantifiers</b></div><div>∃x C(x) — somebody is clever</div><div>∀x C(x) — everybody is clever</div><div><br/></div><div>same priority level as for ¬</div><div><br/></div><div><b>Models</b></div><div>if L(r,j) means Robert loves Jane, it holds in M1 but not M2</div><div><br/></div><div><img src="Predicate%20Logic.resources/screenshot.png" height="264" width="725"/></div><div><br/></div><div>meaning/truth value of a formula from predicate logic depends on underlying model M, consisting of:</div><div><ul><li>set A of elements</li><li>interpretation of constants (r, j)</li><li>interpretation of predicate symbols (L, C, K)</li></ul></div><div><br/></div><div>∀x ϕ is true in M if true for <i>every</i> element in A</div><div>∃x ϕ is true in M if true for <i>some</i> element in A</div><div>for each e ∈ A, ϕ [x := e] is true in M</div><div><br/></div><div><b>Semantic entailment</b></div><div>for formula ϕ, M ⊨ ϕ means that ϕ is true in M</div><div>tautology — true in all models</div><div>contradiction — false in all models</div><div>contingent — true in some model, false in another</div><div>satisfiable — true in some model</div><div><br/></div><div><b>Semantic equivalence</b></div><div>if for all models M, <span> </span>M ⊨ ϕ ⟷ M ⊨ Ψ</div><div>then ϕ ≡ Ψ</div><div><br/></div><div>also, given that “nobody is perfect”, this holds:</div><div>¬∃x P(x) ≡ ∀x ¬P(x)</div><div><br/></div><div><b>Alpha conversion</b></div><div>you can rename bound variables like in lambda calc</div><div>∀x C(x) ≡ ∀y C(y)</div></body></html>